public class Solution813 {
    public double largestSumOfAverages(int[] nums, int k) {
        int n=nums.length;
        double[][] avg=new double[n][n];
        for (int i=0;i<n;i++){
            double total=0;
            for (int j=i;j<n;j++){
                total+=nums[j];
                avg[i][j]=total/(j-i+1);
            }
        }
        double[][] f=new double[n][k+1];
        for (int i=0;i<n;i++){
            f[i][1]=avg[0][i];
            for (int j=2;j<=Math.min(i+1,k);j++){
                f[i][j]=Integer.MIN_VALUE;
                for (int l=j-2;l<i;l++){
                    f[i][j]=Math.max(f[i][j],f[l][j-1]+avg[l+1][i]);
                }
            }
        }
        return f[n-1][k];
    }

    public static void main(String[] args) {
        System.out.println(new Solution813().largestSumOfAverages(new int[]{9,1,2,3,9},3));
    }
}
